package main

import "sort"

//给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
//
// candidates 中的每个数字在每个组合中只能使用 一次 。
//
// 注意：解集不能包含重复的组合。
//
//
//
// 示例 1:
//
//
//输入: candidates = [10,1,2,7,6,1,5], target = 8,
//输出:
//[
//[1,1,6],
//[1,2,5],
//[1,7],
//[2,6]
//]
//
// 示例 2:
//
//
//输入: candidates = [2,5,2,1,2], target = 5,
//输出:
//[
//[1,2,2],
//[5]
//]
//
//
//
// 提示:
//
//
// 1 <= candidates.length <= 100
// 1 <= candidates[i] <= 50
// 1 <= target <= 30
//
// Related Topics 数组 回溯 👍 862 👎 0

//leetcode submit region begin(Prohibit modification and deletion)
// 会有重复元素
func combinationSum2(candidates []int, target int) [][]int {
	//本题的难点在于有重复元素，但是最后输出的时候子集还不能重复，牵扯去重（重点）
	var res [][]int
	var path []int
	sum := 0
	//在求和问题中，要去重，先排序是常见的套路，这也是下面candidates[i]==candidates[i-1]需要的
	sort.Ints(candidates)
	var backTrack func(int)
	//这里的start指的是起始的位置，一般都是0
	backTrack = func(start int) {
		//递归终止条件(往往刚开始都没有path，这一步肯定是越过去的)
		if sum == target {
			//初始化一个path大小的切片（也叫一维数组）命名为temp
			temp := make([]int, len(path))
			//将这个path存入初始的切片temp中
			copy(temp, path)
			//然后将temp切片存入最终要返回的二维数组中
			res = append(res, temp)
		}
		//往往这里才是真正的开始（函数内的头在这）
		//剪枝：sum+candidates[i]<=target
		for i := start; i < len(candidates) && sum+candidates[i] <= target; i++ {
			//同一层去重（这时候排序就派上用场了）
			//注意这个candidates[i]==candidates[i-1]也是很巧妙，为啥是i-1不是i+1？为啥一定要是i>start？仔细品，很有深意
			if i > start && candidates[i] == candidates[i-1] {
				continue
			}
			//将元素的值加起来就是为了后面用来和target对比
			sum += candidates[i]
			//同时别忘了将路径存储起来，最终输出的二维数组要保存的东西
			path = append(path, candidates[i])
			//递归（前进一步）
			backTrack(i + 1)
			//回溯
			//要回弹一步，返回叶子节点的父节点，继续扫描这个父节点的其他子节点
			//这时候sum要减去最后的叶子节点的值
			sum -= candidates[i]
			//path路径也要把叶子节点吐出来
			path = path[:len(path)-1]
		}
	}
	//以上就是backTrack()完整回溯函数
	//从0开始遍历
	//函数外的头
	backTrack(0)
	return res
}

//leetcode submit region end(Prohibit modification and deletion)
